1. Field of the Invention
The present invention relates to a method and device for encoding an object contour by using a centroid. More particularly, the present invention relates to a method for encoding an object contour by sequentially measuring distances between a centroid and boundary pixels on a contour of the object and encoding the distances. The present invention also relates to a device suitable for the above-mentioned method.
2. Description of the Related Arts
Object contour coding is essential in object-based coding for both still images and moving pictures. Particularly, in a low bit rate coding such as MPEG4, the coding scheme has to show a high compression rate in order to minimize the bit amounts of the coded data while it provides a detailed representation of an original contour.
The most widely used contour-coding technique is chain coding which is generally used in computer graphics. In chain coding, a codeword is defined for each direction (among 360.degree.), and a contour is traced in a given direction and encoded by using the codeword defined for the direction. The chain coding, however, results in too much bit allocation and has difficulty in taking into account temporal redundancy in a sequence of images, as in a motion picture, even though there is no loss in contour information and the original contour is recovered accurately.
To overcome these drawbacks of the chain coding, several methods seeking compromise between the accuracy and the bit allocation have been proposed. Though such methods can reduce the amount of generated bits, the fundamental drawbacks of the chain coding persist.
There are many image processing applications which are satisfied with merely a rough representation of an object contour. On such applications, other contour coding methods have been used, which reduce the bit allocation required to encode the contour at the cost of failing to provide complete contour information. One of such methods is polygonal approximation, in which the entire contour of an object is approximated by an inner or outer polygon. Despite its strong advantage in bit economy, the polygonal approximation provides only a very rough representation of the contour.
To circumvent the problem of polygonal approximation, a spline approximation method has been employed. Whereas a contour is approximated by line segments in the conventional polygonal approximation method, the spline approximation achieves a more accurate contour representation with the same number of bits, by using non-linear elements, e.g., curves. Meanwhile, spline approximation may be replaced with a discrete sine transform (DST) operation which renders a detailed representation of a more complex contour but with the efficiency of polygonal approximation.
FIG. 1 conceptually illustrates a contour coding method which uses a combination of polygonal approximation and DST operation. Here, a contour is divided into contour segments 10 and each contour segment is approximated as a line segment by the polygonal approximation. After segmentation or line approximation, i.e., polygon approximation, an approximation error 12 which is the distance between the contour segment and the line segment of the polygon is sampled at a predetermined number of positions or angles along the contour. The sampled error values are encoded by carrying out DST and quantization. This coding exhibits low bit consumption and can represent a contour more accurately.
However, all the coding methods described above are limited to contour coding for still images only.
In a moving picture, since each object in consecutive frames retains nearly the same shape and nearly the same position, temporary redundancy also exists in the contour of the object. Thus, the efficiency of the contour coding for a moving picture can be enhanced by taking advantage of such temporal redundancy. In an example of an object contour coding of a moving picture, the object of a (k)th frame is piled on the object of a (k-1)th frame. Then, parts of the contour which are not duplicated are extracted and chain-coded. However, when the contours change fast, there are so many contour segments to be encoded, and the starting point coordinates should be encoded frequently, so that the coding efficiency deteriorates ultimately.